
\subsection{Problem 6}

Recommended (8 Points): Analyze the fft() function called in task.c. Try to find loop bounds for the Fast Fourier Transform implementation (fixedpoint.c:fp radix2fft withscaling) first. If you have difficulties finding them, add a debug statement and run the transform with different input data sizes. Add flow constraints relating the execution frequency of the inner loops with the function's execution frequency. Finally, try to analyze the execution time using aiT. There is already a timing measurement for the ait in the executable, so it is easy to compare the number of cycles estimated to execute the function. Compare the worst-case number of iterations for the inner loop with and without using these flow constraints. Finally, think about the complexity of calculating loop bounds for FFT. Does the FFT loop bound depend on the input data?
\\
\\
\textbf{Solution:}
\\
\\
\noindent The results of the time measurement can be found in Table~\ref{tab:fft}. Then we analyzed the function \textit{fft()} with and without the flow constraint of the inner loop. The results can be found in Figure~\ref{fig:6with} and Figure~\ref{fig:6without}. The source code with the annotations can be found in Section~\ref{sec:fix}.

\begin{table}
\centering
	\begin{tabular}[!htpb]{|c|c|c|c|c|} 
		\hline
		Name	& Min	& Max & Total & Samples \\
		\hline
		\hline
		Task						& 13059 & 180579 & 2472186 & 18 \\
		Merge\_samples 	& 15907 & 104367 & 234005  & 7 \\
		fft							& 124751 & 124751 & 124751 & 1 \\
		\hline
	\end{tabular} 
	\caption{Measurements function \textit{fft()} \label{tab:fft}}
\end{table} 

\begin{figure}[htbp]
	\centering
		\includegraphics[width=0.90\textwidth]{figures/6_withflow.PNG}
	\caption{Static analysis of \textit{fft()} with flow constraint}
	\label{fig:6with}
\end{figure}

\begin{figure}[htbp]
	\centering
		\includegraphics[width=0.90\textwidth]{figures/6_withoutflow.PNG}
	\caption{Static analysis of \textit{fft()} without flow constraint}
	\label{fig:6without}
\end{figure}

\noindent The results are quite different. With the flow constraint we get as result 159957, without the flow constraint we get as result 2079477. The \textit{fft()} loop bound does depend on how many samples are the input of the function. In our example there are always 64 samples, so the calculation is not dependent on the input data. If one knows how many samples to process then it is easy to calculate the loop bounds.

